#include <cstdio>
#include <string>

using namespace std;

const int maxn=5000;
const int maxm=50000;
const int size=(maxn+maxm+2)*8;
const int oo=1000000000;

struct Flow {
	int c, f;
	int num, nxt, opp;
};

int n, m;
int g[maxn+maxm+2], gg[maxn+maxm+2], tot, x, d[maxn+maxm+2], fa[maxn+maxm+2];
int h, t, queue[maxn+maxm+2], l;
Flow list[size];
int ans;
bool mark[maxn+maxm+2];

void insert(int x, int y, int z){
	tot++; list[tot].num=y; list[tot].c=z; list[tot].f=0; list[tot].nxt=g[x]; list[tot].opp=tot+1; g[x]=tot;
	tot++; list[tot].num=x; list[tot].c=0; list[tot].f=0; list[tot].nxt=g[y]; list[tot].opp=tot-1; g[y]=tot;
}

void bfs(){

	memset( mark, false, sizeof(mark) );
	memset( d, 0, sizeof(d) );
	memset( queue, 0, sizeof(queue) );
	h=0; t=1; mark[0]=true; d[0]=0;
	while (h<t) {
		h++;
		for (l=g[ queue[ h ] ]; l!=0; l=list[ l ].nxt )
			if ( ( list[ l ].c > list[ l ].f ) && (! mark[ list[ l ]. num ] )) {
				t++; queue[t]= list[ l ].num;
				d[ queue[ t ] ]=d[ queue[ h ] ]+1;
				mark[ queue[ t ] ]=true;
			}
	}
}

void dinic() {
	int i, l, x, min, p;
	while (1) {
		bfs();
		if ( ! mark[ n+m+1 ] ) return;
		memset(mark, false, sizeof(mark));
		memset(fa, -1, sizeof(fa) );
		for (i=0; i<=n+m+1; i++) gg[i]=g[i];
		x=0;
		while (! mark[ 0 ]) {
			l=gg[x];
			while ( (l!=0) && ( mark[ list[ l ].num ] || ( d[ list[ l ].num ]-1!=d[ x ] ) || ( list[ l ].c == list[ l ].f ) ) )
				l=list[l].nxt;
			if (l==0) {
				mark[ x ]=true;
				x=fa[ x ];
			} else {
				gg[ x ]=l;
				fa[ list[ l ].num ]=x;
				x=list[ l ].num;
				if (x==n+m+1) {
					min=oo;
					while (fa[x]!=-1) {
						if (list[ gg[ fa[ x ] ] ].c-list[ gg[ fa[ x ] ] ].f<=min) {
							min=list[ gg[ fa[ x ] ] ].c - list[ gg[ fa[ x ] ] ].f;
							p=fa[x];
						}
						x=fa[ x ];
					}
					x=n+m+1;
					while (fa[ x ]!=-1){
						list[ gg[ fa[ x ] ] ].f+=min;
						list[ list[ gg[ fa[ x ] ] ].opp ].f-=min;
						x=fa[x];
					}
					x=p;
					ans-=min;
                		}
			}
		}
	}
}

int main(){
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
	int test, i;
	scanf("%d", &test);
	for (; test; test--){
		scanf("%d %d", &n, &m);
		memset(g, 0, sizeof(g));
		tot=0;

		int x, y, z;
		for (i=1; i<=n; i++){
			scanf("%d", &x);
			insert(0, i, x);
		}
		ans=0;
		for (i=1; i<=m; i++){
			scanf("%d %d %d", &x, &y, &z);
			insert(x, n+i, oo);
			insert(y, n+i, oo);
			insert(n+i, n+m+1, z);
			ans+=z;
		}
		dinic();
    		printf("%d\n", ans);
	}
}
